package com.leetcode.a003;

import java.util.HashMap;
import java.util.Map;

/**
 * @author zhengqn
 * @Title: LengthOfLongestSubstring
 * @Description: 无重复字符的最长子串
 * @date 2019/12/20 10:01
 */
public class LengthOfLongestSubstring {

    public int lengthOfLongestSubstring(String s){
        if (s == null) {
            return 0;
        }
        int maxLen = 0;
        // map中存放所有已遍历的字符
        Map<Character, Integer> map = new HashMap<>(s.length());
        // 记计算最大长度的起始位置
        int p = 0;
        //对字符串进行循环遍历
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            // 判断当前字符在之前有没有出现过
            if (map.containsKey(c)) {
                // 上一个出现相同字符的位置。取最大值，是防止回滚
                // 比如 abba ，读取第二个a的时候，不能去第一个a的下标，这样计算出来的是包含了中间重复部分的
                p = Math.max(map.get(c)+1, p);
            }
            // 遍历的字符放入到map中
            map.put(s.charAt(i), i);
            maxLen = Math.max(maxLen, i-p+1);
        }

        return maxLen;
    }

    public static void main(String[] args) {
        LengthOfLongestSubstring lls = new LengthOfLongestSubstring();
        System.out.println(lls.lengthOfLongestSubstring("pwwkew"));

    }
}
